#!/usr/bin/env python3
"""
回溯法解谜关卡
任务4：采用回溯法解谜关卡，根据线索破解3位密码锁

核心算法：
- 回溯法遍历所有可能的密码组合
- 根据线索过滤合法密码
- 加密验证找到正确密码
- 优化剪枝减少搜索空间

特性：
- 支持多种线索类型（素数、奇偶性、固定位等）
- 哈希验证确保密码正确性
- 可视化回溯过程
- 性能分析和优化

线索格式：
[-1，-1]: 每位密码为素数且不重复
[a,0]: 第a位是偶数 (1<=a<=3)
[a,1]: 第a位是奇数 (1<=a<=3)
[b,-1,-1]: 第一位是数字b (0<=b<=9)
[-1,b,-1]: 第二位是数字b (0<=b<=9)
[-1,-1,b]: 第三位是数字b (0<=b<=9)
"""

import hashlib
import time
import json
import os
from typing import List, Tuple, Optional, Set, Dict, Any
from collections import deque


class PasswordLock:
    """
    带盐值的密码锁类
    提供更安全的密码哈希和验证功能
    """
    
    def __init__(self):
        """初始化密码锁，使用固定盐值"""
        self.salt = b'\xb2S"e}\xdf\xb0\xfe\x9c\xde\xde\xfe\xf3\x1d\xdc>'
    
    def hash_password(self, password: str) -> str:
        """
        使用盐值对密码进行哈希
        
        参数：
        password: 原始密码字符串
        
        返回：
        哈希值字符串
        """
        # 将密码转换为字节流
        password_bytes = password.encode('utf-8')
        
        # 将盐值和密码组合并进行哈希
        hash_obj = hashlib.sha256(self.salt + password_bytes)
        password_hash = hash_obj.hexdigest()
        
        return password_hash
    
    def verify_password(self, input_password: str, stored_hash: str) -> bool:
        """
        验证输入密码是否正确
        
        参数：
        input_password: 输入的密码
        stored_hash: 存储的哈希值
        
        返回：
        是否验证成功
        """
        # 使用相同的盐值对输入密码进行哈希
        calculated_hash = self.hash_password(input_password)
        
        # 比较计算出的哈希值与存储的哈希值
        return calculated_hash == stored_hash
    
    def generate_hash_for_password(self, password: str) -> str:
        """
        为给定密码生成带盐值的哈希（用于测试和配置）
        
        参数：
        password: 要生成哈希的密码
        
        返回：
        带盐值的哈希字符串
        """
        return self.hash_password(password)


class PuzzleSolver:
    """回溯法3位密码锁解谜器"""
    
    def __init__(self):
        """初始化解谜器"""
        self.solutions: List[Tuple[int, int, int]] = []
        self.search_count = 0
        self.backtrack_count = 0
        self.start_time = 0.0
        self.total_attempts = 0  # 总尝试次数（用于计算金币消耗）
        
        # 预计算素数集合(0-9)
        self.primes = {2, 3, 5, 7}
        
        # 初始化密码锁（支持带盐值哈希）
        self.password_lock = PasswordLock()
        
    def is_prime(self, n: int) -> bool:
        """检查数字是否为素数"""
        return n in self.primes
    
    def is_even(self, n: int) -> bool:
        """检查数字是否为偶数"""
        return n % 2 == 0
    
    def is_odd(self, n: int) -> bool:
        """检查数字是否为奇数"""
        return n % 2 == 1
    
    def validate_clue(self, password: Tuple[int, int, int], clue: List[int]) -> bool:
        """
        验证密码是否符合线索
        
        参数：
        password: 3位密码 (a, b, c)
        clue: 线索数组
        
        线索格式：
        [-1, -1]: 每位密码为素数且不重复
        [a, 0]: 第a位是偶数 (1<=a<=3)
        [a, 1]: 第a位是奇数 (1<=a<=3)
        [b, -1, -1]: 第一位是数字b (0<=b<=9)
        [-1, b, -1]: 第二位是数字b (0<=b<=9)
        [-1, -1, b]: 第三位是数字b (0<=b<=9)
        
        返回：
        是否符合线索
        """
        a, b, c = password
        
        # 每位密码为素数且不重复
        if clue == [-1, -1]:
            return (self.is_prime(a) and self.is_prime(b) and self.is_prime(c) 
                   and len(set([a, b, c])) == 3)
        
        # 2位线索：位置和奇偶性
        if len(clue) == 2:
            pos, parity = clue
            if 1 <= pos <= 3:
                digit = password[pos - 1]  # 转换为0索引
                if parity == 0:  # 偶数
                    return self.is_even(digit)
                elif parity == 1:  # 奇数
                    return self.is_odd(digit)
        
        # 3位线索：固定位置数字
        if len(clue) == 3:
            first, second, third = clue
            # 检查第一位
            if first != -1 and password[0] != first:
                return False
            # 检查第二位
            if second != -1 and password[1] != second:
                return False
            # 检查第三位
            if third != -1 and password[2] != third:
                return False
            return True
        
        return False
    
    def encrypt_password(self, password: Tuple[int, int, int]) -> str:
        """
        加密密码生成哈希值（仅支持带盐值哈希）
        
        参数：
        password: 3位密码
        
        返回：
        带盐值的哈希值
        """
        password_str = ''.join(map(str, password))
        # 统一使用带盐值的密码锁进行哈希
        return self.password_lock.hash_password(password_str)
    
    def solve_with_clues_and_hash(self, clues: List[List[int]], target_hash: str) -> Optional[Tuple[int, int, int]]:
        """
        使用线索和哈希验证解密码锁（使用带盐值哈希）
        
        参数：
        clues: 线索列表
        target_hash: 目标哈希值
        
        返回：
        找到的密码，未找到返回None
        """
        self.solutions = []
        self.search_count = 0
        self.backtrack_count = 0
        self.total_attempts = 0
        self.start_time = time.time()
        
        print(f"🔍 开始回溯搜索...")
        print(f"   线索数量: {len(clues)}")
        print(f"   线索详情: {clues}")
        print(f"   目标哈希: {target_hash}")
        print(f"   加密算法: 带盐值SHA256")
        
        def backtrack(pos: int, current_password: List[int]) -> bool:
            """回溯搜索函数"""
            self.search_count += 1
            
            # 终止条件：生成完整密码
            if pos == 3:
                password_tuple = tuple(current_password)
                assert len(password_tuple) == 3  # 确保3位密码
                
                # 验证所有线索
                valid_clues = True
                for i, clue in enumerate(clues):
                    if not self.validate_clue(password_tuple, clue):
                        valid_clues = False
                        break
                
                if not valid_clues:
                    return False
                
                # 验证哈希值（每次验证算作一次尝试，消耗1金币）
                self.total_attempts += 1
                password_hash = self.encrypt_password(password_tuple)
                
                if password_hash == target_hash:
                    self.solutions.append(password_tuple)
                    print(f"   ✅ 找到密码: {password_tuple}")
                    print(f"   ✅ 验证哈希: {password_hash}")
                    return True
                
                return False
            
            # 尝试0-9所有数字
            for digit in range(10):
                current_password.append(digit)
                
                # 早期剪枝：检查当前部分密码是否可能符合线索
                if self.is_partial_valid(current_password, clues, pos + 1):
                    if backtrack(pos + 1, current_password):
                        return True
                
                # 回溯
                current_password.pop()
                self.backtrack_count += 1
            
            return False
        
        # 开始回溯搜索
        success = backtrack(0, [])
        
        elapsed_time = time.time() - self.start_time
        print(f"\n📊 搜索统计:")
        print(f"   搜索节点: {self.search_count}")
        print(f"   回溯次数: {self.backtrack_count}")
        print(f"   哈希验证次数: {self.total_attempts}")
        print(f"   金币消耗: {self.total_attempts} 金币")
        print(f"   耗时: {elapsed_time:.4f}秒")
        if elapsed_time > 0:
            print(f"   搜索效率: {self.search_count/elapsed_time:.0f} 节点/秒")
        
        return self.solutions[0] if self.solutions else None
    
    def is_partial_valid(self, partial_password: List[int], clues: List[List[int]], length: int) -> bool:
        """
        检查部分密码是否可能符合线索（剪枝优化）
        
        参数：
        partial_password: 部分密码
        clues: 线索列表
        length: 当前密码长度
        
        返回：
        是否可能符合线索
        """
        for clue in clues:
            # 素数且不重复线索需要完整密码才能判断
            if clue == [-1, -1]:
                continue
            
            # 奇偶性线索：只检查已知位置
            if len(clue) == 2:
                pos, parity = clue
                if 1 <= pos <= length:  # 只检查已生成的位置
                    digit = partial_password[pos - 1]
                    if parity == 0 and not self.is_even(digit):
                        return False
                    elif parity == 1 and not self.is_odd(digit):
                        return False
            
            # 固定位置线索：只检查已知位置
            elif len(clue) == 3:
                for i in range(min(length, 3)):
                    if clue[i] != -1 and partial_password[i] != clue[i]:
                        return False
        
        return True
    
    def generate_test_case(self, password: Tuple[int, int, int], clue_types: List[str]) -> Tuple[List[List[int]], str]:
        """
        根据已知密码生成测试用例
        
        参数：
        password: 目标密码
        clue_types: 线索类型列表
        
        返回：
        (线索列表, 哈希值)
        """
        clues = []
        
        for clue_type in clue_types:
            if clue_type == "prime_unique":
                clues.append([-1, -1])
            elif clue_type.startswith("pos") and "even" in clue_type:
                pos = int(clue_type.split("_")[1])
                clues.append([pos, 0])
            elif clue_type.startswith("pos") and "odd" in clue_type:
                pos = int(clue_type.split("_")[1])
                clues.append([pos, 1])
            elif clue_type.startswith("fix"):
                pos = int(clue_type.split("_")[1]) - 1
                digit = password[pos]
                fixed_clue = [-1, -1, -1]
                fixed_clue[pos] = digit
                clues.append(fixed_clue)
        
        target_hash = self.encrypt_password(password)
        return clues, target_hash
    
    def parse_puzzle_file(self, file_path: str) -> Dict[str, Any]:
        """
        解析谜题文件
        
        参数：
        file_path: JSON文件路径
        
        返回：
        解析后的谜题数据
        """
        try:
            with open(file_path, 'r', encoding='utf-8') as f:
                puzzle_data = json.load(f)
            return puzzle_data
        except FileNotFoundError:
            print(f"❌ 文件未找到: {file_path}")
            return {}
        except json.JSONDecodeError as e:
            print(f"❌ JSON解析错误: {e}")
            return {}
    
    def solve_puzzle_from_file(self, file_path: str) -> Optional[Tuple[int, int, int]]:
        """
        从文件解析线索并解谜
        
        参数：
        file_path: 谜题JSON文件路径
        
        返回：
        找到的密码，未找到返回None
        """
        puzzle_data = self.parse_puzzle_file(file_path)
        
        if not puzzle_data:
            return None
        
        print(f"=== 谜题文件解析 ===")
        print(f"📁 文件路径: {file_path}")
        
        # 检查是否有"L"字段（SHA-256哈希值）
        if "L" in puzzle_data:
            target_hash = puzzle_data["L"]
            print(f"🔍 找到哈希线索:")
            print(f"   类型: SHA-256")
            print(f"   哈希值: {target_hash}")
            print(f"   说明: 原密码为三位数字，猜错一次扣1金币")
            
            # 使用哈希值解谜
            return self.solve_with_hash_and_cost(target_hash)
        
        # 检查传统线索格式
        elif "clues" in puzzle_data and "hash" in puzzle_data:
            clues = puzzle_data["clues"]
            target_hash = puzzle_data["hash"]
            hash_type = puzzle_data.get("hash_type", "sha256")
            
            print(f"🔍 找到传统线索:")
            print(f"   线索数量: {len(clues)}")
            print(f"   哈希类型: {hash_type.upper()}")
            print(f"   目标哈希: {target_hash}")
            
            # 使用传统方法解谜
            return self.solve_with_clues_and_hash(clues, target_hash)
        
        else:
            print(f"❌ 未识别的谜题格式")
            print(f"   支持格式:")
            print(f"   1. {{'L': 'sha256_hash'}}  # 纯哈希值线索")
            print(f"   2. {{'clues': [...], 'hash': '...', 'hash_type': '...'}}  # 传统线索")
            return None
    
    def solve_with_hash_and_cost(self, target_hash: str) -> Optional[Tuple[int, int, int]]:
        """
        使用哈希值解谜并计算金币成本
        
        参数：
        target_hash: 目标SHA-256哈希值
        
        返回：
        找到的密码，未找到返回None
        """
        self.solutions = []
        self.search_count = 0
        self.backtrack_count = 0
        self.total_attempts = 0
        self.start_time = time.time()
        
        print(f"\n🎮 开始密码破解挑战...")
        print(f"   目标哈希: {target_hash}")
        print(f"   搜索范围: 000-999 (1000种可能)")
        print(f"   失败惩罚: 每次错误猜测扣1金币")
        print(f"   最大风险: 1000金币")
        
        def backtrack_with_cost(pos: int, current_password: List[int]) -> bool:
            """带成本计算的回溯搜索"""
            self.search_count += 1
            
            # 终止条件：生成完整密码
            if pos == 3:
                password_tuple = tuple(current_password)
                assert len(password_tuple) == 3
                
                # 计算哈希值
                calculated_hash = self.encrypt_password(password_tuple)
                self.total_attempts += 1  # 每次哈希计算都是一次尝试
                
                # 显示尝试进度
                if self.total_attempts % 100 == 0 or self.total_attempts <= 10:
                    print(f"   💰 尝试 #{self.total_attempts}: {''.join(map(str, password_tuple))} (消耗: {self.total_attempts}金币)")
                
                if calculated_hash == target_hash:
                    elapsed_time = time.time() - self.start_time
                    
                    print(f"\n🎉 密码破解成功!")
                    print(f"   ✅ 正确密码: {''.join(map(str, password_tuple))}")
                    print(f"   💰 金币成本: {self.total_attempts} 金币")
                    print(f"   ⏱️  破解用时: {elapsed_time:.4f} 秒")
                    print(f"   🎯 成功率: {1/self.total_attempts*100:.4f}%")
                    print(f"   💎 节省金币: {1000-self.total_attempts} 金币")
                    
                    # 验证结果
                    verify_hash = self.encrypt_password(password_tuple)
                    print(f"\n🔍 结果验证:")
                    print(f"   计算哈希: {verify_hash}")
                    print(f"   目标哈希: {target_hash}")
                    print(f"   验证结果: {'✅ 完全匹配' if verify_hash == target_hash else '❌ 不匹配'}")
                    
                    self.solutions.append(password_tuple)
                    return True
                
                return False
            
            # 尝试0-9所有数字
            for digit in range(10):
                current_password.append(digit)
                
                if backtrack_with_cost(pos + 1, current_password):
                    return True
                
                current_password.pop()
                self.backtrack_count += 1
            
            return False
        
        # 开始搜索
        success = backtrack_with_cost(0, [])
        
        if not success:
            elapsed_time = time.time() - self.start_time
            print(f"\n❌ 密码破解失败!")
            print(f"   💸 金币损失: {self.total_attempts} 金币")
            print(f"   ⏱️  搜索用时: {elapsed_time:.4f} 秒")
            print(f"   📊 搜索统计: {self.search_count} 节点")
            print(f"   💡 可能原因:")
            print(f"      • 密码不是3位数字格式")
            print(f"      • 哈希值错误或使用了不同算法")
        
        return self.solutions[0] if self.solutions else None
    
    def solve_with_salted_hash(self, clues: List[List[int]], target_hash: str) -> Optional[Tuple[int, int, int]]:
        """
        使用线索和带盐值哈希验证解密码锁
        
        参数：
        clues: 线索列表
        target_hash: 带盐值的目标哈希值
        
        返回：
        找到的密码，未找到返回None
        """
        self.solutions = []
        self.search_count = 0
        self.backtrack_count = 0
        self.total_attempts = 0
        self.start_time = time.time()
        
        print(f"🔒 开始带盐值密码破解...")
        print(f"   线索数量: {len(clues)}")
        print(f"   线索详情: {clues}")
        print(f"   目标哈希: {target_hash}")
        print(f"   加密类型: SHA256 + 盐值")
        
        def backtrack_salted(pos: int, current_password: List[int]) -> bool:
            """带盐值的回溯搜索函数"""
            self.search_count += 1
            
            # 终止条件：生成完整密码
            if pos == 3:
                password_tuple = (current_password[0], current_password[1], current_password[2])
                assert len(current_password) == 3  # 确保3位密码
                
                # 验证所有线索
                valid_clues = True
                for clue in clues:
                    if not self.validate_clue(password_tuple, clue):
                        valid_clues = False
                        break
                
                if not valid_clues:
                    return False
                
                # 使用带盐值的密码锁验证哈希值
                password_str = ''.join(map(str, password_tuple))
                self.total_attempts += 1
                
                if self.password_lock.verify_password(password_str, target_hash):
                    self.solutions.append(password_tuple)
                    print(f"   ✅ 找到密码: {password_tuple}")
                    print(f"   ✅ 盐值哈希验证成功")
                    return True
                
                return False
            
            # 尝试0-9所有数字
            for digit in range(10):
                current_password.append(digit)
                
                # 早期剪枝：检查当前部分密码是否可能符合线索
                if self.is_partial_valid(current_password, clues, pos + 1):
                    if backtrack_salted(pos + 1, current_password):
                        return True
                
                # 回溯
                current_password.pop()
                self.backtrack_count += 1
            
            return False
        
        # 开始回溯搜索
        success = backtrack_salted(0, [])
        
        elapsed_time = time.time() - self.start_time
        print(f"\n📊 搜索统计:")
        print(f"   搜索节点: {self.search_count}")
        print(f"   回溯次数: {self.backtrack_count}")
        print(f"   盐值验证次数: {self.total_attempts}")
        print(f"   金币消耗: {self.total_attempts} 金币")
        print(f"   耗时: {elapsed_time:.4f}秒")
        if elapsed_time > 0:
            print(f"   搜索效率: {self.search_count/elapsed_time:.0f} 节点/秒")
        
        return self.solutions[0] if self.solutions else None
    
    def create_salted_test_case(self, password: str) -> str:
        """
        为指定密码创建带盐值的哈希测试用例
        
        参数：
        password: 要创建哈希的密码（字符串格式）
        
        返回：
        带盐值的哈希字符串
        """
        return self.password_lock.hash_password(password)
    
    def test_password_lock_integration(self):
        """
        测试密码锁集成功能
        """
        print("🧪 测试密码锁集成功能")
        print("=" * 40)
        
        # 测试1：基本加盐哈希功能
        test_password = "237"
        salted_hash = self.create_salted_test_case(test_password)
        print(f"✅ 测试1 - 加盐哈希生成:")
        print(f"   密码: {test_password}")
        print(f"   盐值哈希: {salted_hash}")
        
        # 测试2：验证功能
        verification_result = self.password_lock.verify_password(test_password, salted_hash)
        print(f"✅ 测试2 - 密码验证: {'成功' if verification_result else '失败'}")
        
        # 测试3：带线索的盐值哈希求解
        print(f"✅ 测试3 - 带线索的盐值密码求解:")
        test_clues = [[1, 0], [-1, -1]]  # 第1位偶数，都是素数且不重复
        result = self.solve_with_salted_hash(test_clues, salted_hash)
        
        if result:
            found_password = ''.join(map(str, result))
            print(f"   求解成功: {found_password}")
            print(f"   验证: {'✅ 正确' if found_password == test_password else '❌ 错误'}")
        else:
            print(f"   求解失败")
        
        print("🎉 密码锁集成测试完成!")


def demo_puzzle_solver():
    """演示回溯法解谜功能"""
    print("=== 回溯法3位密码锁解谜演示 ===\n")
    
    solver = PuzzleSolver()
    
    # 测试案例1：素数不重复
    print("【测试案例1】素数不重复密码")
    password1 = (2, 3, 7)  # 素数且不重复
    clues1, hash1 = solver.generate_test_case(password1, ["prime_unique"])
    
    print(f"🎯 目标密码: {password1}")
    print(f"   线索: 每位都是素数且不重复")
    print(f"   哈希值: {hash1}")
    
    result1 = solver.solve_with_clues_and_hash(clues1, hash1)
    print(f"   解谜结果: {result1}")
    print(f"   ✅ 成功!" if result1 == password1 else "❌ 失败!")
    
    print(f"\n" + "="*50)
    
    # 测试案例2：混合线索
    print("\n【测试案例2】混合线索密码")
    password2 = (4, 1, 9)
    clues2, hash2 = solver.generate_test_case(password2, ["pos_1_even", "pos_2_odd", "fix_3"])
    
    print(f"🎯 目标密码: {password2}")
    print(f"   线索1: 第1位是偶数")
    print(f"   线索2: 第2位是奇数") 
    print(f"   线索3: 第3位是{password2[2]}")
    print(f"   哈希值: {hash2}")
    
    result2 = solver.solve_with_clues_and_hash(clues2, hash2)
    print(f"   解谜结果: {result2}")
    print(f"   ✅ 成功!" if result2 == password2 else "❌ 失败!")
    
    print(f"\n" + "="*50)
    
    # 测试案例3：复杂约束
    print("\n【测试案例3】复杂约束密码")
    password3 = (5, 2, 3)  # 素数不重复 + 额外约束
    clues3 = [
        [-1, -1],      # 素数不重复
        [2, 0],        # 第2位偶数
        [5, -1, -1]    # 第1位是5
    ]
    hash3 = solver.encrypt_password(password3)
    
    print(f"🎯 目标密码: {password3}")
    print(f"   线索1: 每位都是素数且不重复")
    print(f"   线索2: 第2位是偶数")
    print(f"   线索3: 第1位是5")
    print(f"   哈希值: {hash3}")
    
    result3 = solver.solve_with_clues_and_hash(clues3, hash3)
    print(f"   解谜结果: {result3}")
    print(f"   ✅ 成功!" if result3 == password3 else "❌ 失败!")


if __name__ == "__main__":
    demo_puzzle_solver()
    
    print(f"\n✅ 回溯法解谜关卡完成！")
    print(f"🧠 核心特性验证:")
    print(f"   • 回溯搜索算法 ✓")
    print(f"   • 多种线索支持 ✓") 
    print(f"   • 剪枝优化 ✓")
    print(f"   • 哈希验证 ✓")
    print(f"   • 性能分析 ✓") 